//
// Created by user_xk on 2023/3/8.
//

#include <iostream>
#include "solution.h"
#include "string"
#include "algorithm"
#include "queue"
#include "set"

#include "exception/FileContentException.h"
#include "exception/FileEmptyException.h"
#include "exception/NonMatchedChainException.h"
#include "exception/CircleTypeException.h"
#include "exception/DuplicatedWordException.h"
#include "exception/OneLetterWordException.h"
#include "exception/WordsOverflowException.h"
#include "exception/ResultOverflowException.h"

using namespace std;

// declare func
bool is_end_word(char c);
string get_next_word(FILE *file);

bool check_circle();
vector<Record> get_all_records(char head_letter, char tail_letter, char head_not_letter, bool is_circle);
vector<Record> get_main_records(char head_letter, char head_not_letter, bool is_circle);
vector<Record> get_first_letter_main_records(int head, bool is_circle);
vector<Record> get_all_child_records(vector<Record> main_records, char tail_letter);
vector<Record> get_child_records(Record record, char tail_letter);
vector<string> get_chain_by_record(Record record);
string get_one_max_length_letter_chain_by_record(Record record, bool is_circle);

void print_records(vector<Record> records);
string print_chains(vector<string> chains);
string print_max_chain(string chain);


bool has_word = false;
bool file_end = false;

bool print_check = false;


string solution(FILE* file, int type, char head_letter, char tail_letter, char head_not_letter, bool is_circle) {
    // type: 0 -> all_chain, 1 -> max_word_length, 2 -> max_letter_length
    // head_letter, tail_letter, head_not_letter can be NULL
    // other params must not be NULL, which means this func does not conclude the function of check the rightness of command

    int words_num = init_graph(file);

    bool real_circle = check_circle();
    if (print_check) {
        cout << "is_circle: " << (real_circle ? "true" : "false") << "\n";
    }
    if (is_circle != real_circle) {
//        cout << "circle type error!\n";
        throw CircleTypeException(real_circle);
    }

    if (type != 0 && real_circle && words_num > 100) {
        throw WordsOverflowException(true);
    }
    else if (!real_circle && words_num > 10000) {
        throw WordsOverflowException(false);
    }

    if (type == 0) {
        return get_all_chain(head_letter, tail_letter, head_not_letter, is_circle);
    }
    else {
        return get_max_length_chain(type == 1, head_letter, tail_letter, head_not_letter, is_circle);
    }
}


int init_graph(FILE* file) {
    for (auto & i : graph) {
        for (auto edge : i) {
            edge.words.clear();
            while (!edge.words_priority_queue.empty()) {
                edge.words_priority_queue.pop();
            }
            edge.is_free = false;
            edge.num = 0;
        }
    }


    set<string> words_set;

    while (!file_end) {
        string token;
        //为了判断连续空格
        while (token.empty()) {
            token = get_next_word(file);
            if (file_end && token.empty()) {
                if (!has_word) {
                    throw FileEmptyException();
                }

                return (int) words_set.size();
            }
        }

        transform(token.begin(), token.end(), token.begin(), ::tolower);

        if (token.length() == 1) {
            throw OneLetterWordException(token);
        }
        if (words_set.find(token) != words_set.end()) {
            throw DuplicatedWordException(token);
        }
        words_set.insert(token);

        has_word = true;

        int begin = token[0] - 'a', end = token[token.length() - 1] - 'a';
        // for edge
        graph[begin][end].words.emplace_back(token);
        graph[begin][end].words_priority_queue.push(token);
        graph[begin][end].num++;
        graph[begin][end].is_free = true;

        // for vertex, not care self-circle
        if (begin != end) {
            vertexes[begin].out_degrees.insert(end);
            vertexes[end].in_degrees.insert(begin);
        }
    }

    return (int) words_set.size();
}

// 对于h, t, j，输入0代表无限制
string get_all_chain(char head_letter, char tail_letter, char head_not_letter, bool is_circle) {
    vector<string> chains;
    vector<Record> all_records = get_all_records(head_letter, tail_letter, head_not_letter, is_circle);

    if (all_records.empty()) {
        throw NonMatchedChainException();
    }

    for (Record record : all_records) {
        vector<string> now = get_chain_by_record(record);
        chains.insert(chains.end(), now.begin(), now.end());
    }

    return print_chains(chains);
}

string get_max_length_chain(bool is_word, char head_letter, char tail_letter, char head_not_letter, bool is_circle) {
    string max_length_chain;
    string output;
    vector<Record> all_records =  tail_letter != 0 ? get_all_records(head_letter, tail_letter, head_not_letter, is_circle) :
            get_main_records(head_letter, head_not_letter, is_circle);

    int max_length = 0;

    if (all_records.empty()) {
        throw NonMatchedChainException();
    }

    if (is_word) {
        Record max_record;

        for (Record record : all_records) {
            if (record.nodes.size() > max_length) {
                max_length = record.nodes.size();
                max_record = record;
            }
        }

        max_length_chain = get_one_max_length_letter_chain_by_record(max_record, is_circle);

        if (print_check) {
            cout << max_length_chain << "\n";
        }
        else {
            output = print_max_chain(max_length_chain);
        }

    }
    else {
        string max_chain;

        for (Record record : all_records) {
            string now_chain =  get_one_max_length_letter_chain_by_record(record, is_circle);

            if (max_length < now_chain.length()) {
                max_length = now_chain.length();
                max_chain = now_chain;
            }
        }

        max_length_chain =  max_chain;

        if (print_check) {
            cout << max_length_chain << "\n";
        }
        else {
            output = print_max_chain(max_length_chain);
        }
    }

    return output;
}


string get_next_word(FILE *file) {
    string token;
    char now_char = (char) fgetc(file);
    while (!is_end_word(now_char)) {
        if (!isalpha(now_char)) {
            string now_str;
            if (now_char > 0) now_str += now_char;
            else {
                now_str += now_char;
                now_char = (char) fgetc(file);
                now_str += now_char;
                now_char = (char) fgetc(file);
                now_str += now_char;
            }
            throw FileContentException(now_str);
        }
        token += now_char;
        now_char = (char) fgetc(file);
    }
    return token;
}

bool is_end_word(char c) {
    if (c == EOF) {
        file_end = true;
    }
    return c == EOF || c == ' ' || c == '\n';
}

bool check_circle() {
    // check letter circle by itself, such as 'aba' and 'aca'
    for (int i = 0;i < 26;i++) {
        if (graph[i][i].words.size() > 1) {
            return true;
        }
    }

    // by topo_sort
    queue<int> q;
    int *in_degree = new int [26] ();
    int in_empty_count = 0;

    for (int i = 0; i < 26; ++i) {
        in_degree[i] = vertexes[i].in_degrees.size();
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int begin = q.front();
        q.pop();
        in_empty_count++;
        for (int end : vertexes[begin].out_degrees) {
            in_degree[end]--;
            if (in_degree[end] == 0) {
                q.push(end);
            }
        }
    }

    return in_empty_count != 26;
}

// 主链处理首字母，子链处理尾字母
vector<Record> get_all_records(char head_letter, char tail_letter, char head_not_letter, bool is_circle) {
    vector<Record> main_records = get_main_records(head_letter, head_not_letter, is_circle);

    if (print_check) {
        print_records(main_records);
    }

    // only have the vertex of start
    if (main_records.empty()) {
        throw NonMatchedChainException();
    }

    vector<Record> all_records = get_all_child_records(main_records, tail_letter);

    return all_records;
}

vector<Record> get_main_records(char head_letter, char head_not_letter, bool is_circle) {
    vector<Record> main_records;

    // get all main records which are satisfied with head, head_not
    if (head_letter == 0) {
        for (int i = 0; i < 26; ++i) {
            char head = i + 'a';
            if (head != head_not_letter) {
                vector<Record> head_vectors = get_first_letter_main_records(head - 'a', is_circle);
                for (Record record: head_vectors) {
                    if (record.nodes.size() > 2) {
                        main_records.emplace_back(record);
                    }
                }
            }
        }
    }
    else if (head_letter != head_not_letter) {
        vector<Record> head_vectors = get_first_letter_main_records(head_letter - 'a', is_circle);
        for (Record record: head_vectors) {
            if (record.nodes.size() > 2) {
                main_records.emplace_back(record);
            }
        }
    }

    return main_records;
}

vector<Record> get_first_letter_main_records(int head, bool is_circle) {
    vector<Record> records;
    bool is_leaf = true;

    for (int i = 0; i < 26; ++i) {
        bool is_empty = !graph[head][i].words.empty() && (!is_circle ? graph[head][i].is_free : graph[head][i].num > 0);
        if (is_empty) {
            is_leaf = false;

            if (is_circle) {
                graph[head][i].num--;
            }
            else {
                graph[head][i].is_free = false;
            }
            vector<Record> child_records = get_first_letter_main_records(i, is_circle);
            if (is_circle) {
                graph[head][i].num++;
            }
            else {
                graph[head][i].is_free = true;
            }

            for (Record record : child_records) {
                record.nodes.insert(record.nodes.cbegin(), head);
                records.emplace_back(record);
            }
        }
    }

    if (is_leaf) {
        Record record;
        record.nodes.emplace_back(head);
        records.emplace_back(record);
    }

    return records;
}

vector<Record> get_all_child_records(vector<Record> main_records, char tail_letter) {
    vector<Record> all_records;
    set<Record, cmp_record> records_set;

    for (Record record : main_records) {
        vector<Record> child_record = get_child_records(record, tail_letter);

        for (Record record : child_record) {
            if (records_set.find(record) == records_set.end()) {
                records_set.insert(record);
                all_records.emplace_back(record);
            }
        }

//        all_records.insert(all_records.cend(), child_record.begin(), child_record.end());
    }

    return all_records;
}

vector<Record> get_child_records(Record record, char tail_letter) {
    vector<Record> child_records;
    int length = record.nodes.size();

    for (int i = 0;i < length - 2;i++) {
        Record child_record;
        if (tail_letter == 0 || record.nodes.at(length - 1 - i) == tail_letter - 'a') {
            child_record.nodes.insert(child_record.nodes.cbegin(), record.nodes.begin(), record.nodes.end() - i);
            child_records.emplace_back(child_record);
        }
    }

    return child_records;
}

vector<string> get_chain_by_record(Record record) {
    int begin = record.nodes.at(0), end = record.nodes.at(1);
    vector<string> chains;

    if (record.nodes.size() > 2) {
        Record child_record;
        child_record.nodes.assign(record.nodes.begin() + 1, record.nodes.end());

        int words_num = graph[begin][end].words.size();
        for (int i = 0;i < words_num; i++) {
            string now_word = graph[begin][end].words.at(i);

            graph[begin][end].words.erase(remove(graph[begin][end].words.begin(), graph[begin][end].words.end(),
                                                 now_word), graph[begin][end].words.end());
            vector<string> child_chains = get_chain_by_record(child_record);
            graph[begin][end].words.insert(graph[begin][end].words.begin() + i, now_word);

            for (string child_chain : child_chains) {
                chains.emplace_back(now_word + " " + child_chain);
            }
        }
    }
    else {
        for (string now_word : graph[begin][end].words) {
            chains.emplace_back(now_word);
        }
    }

    return chains;
}

string get_one_max_length_letter_chain_by_record(Record record, bool is_circle) {
    string chain;

    if (is_circle) {
        vector<string> pop_words;

        for (int i = 0;i < (int) record.nodes.size() - 1;i++) {
            int begin = record.nodes.at(i);
            int end = record.nodes.at(i + 1);

            string word = graph[begin][end].words_priority_queue.top();
            pop_words.emplace_back(word);
            graph[begin][end].words_priority_queue.pop();
            chain += word + " ";
        }

        for (int i = 0;i < (int) record.nodes.size() - 1;i++) {
            int begin = record.nodes.at(i);
            int end = record.nodes.at(i + 1);

            graph[begin][end].words_priority_queue.push(pop_words.at(i));
        }
    }
    else {
        for (int i = 0;i < (int) record.nodes.size() - 1;i++) {
            int begin = record.nodes.at(i);
            int end = record.nodes.at(i + 1);

            chain += graph[begin][end].words_priority_queue.top() + " ";
        }
    }

    return chain.substr(0, chain.size() - 1);
}

// print for debug
void print_records(vector<Record> records) {
    for (Record record : records) {
        for (int i : record.nodes) {
            cout << (char) (i + 'a') << " ";
        }
        cout << "\n";
    }
    cout << "------------------\n";
}

string print_chains(vector<string> chains) {
    if (chains.size() > 20000) {
        throw ResultOverflowException();
    }

    string output = to_string(chains.size()).append("\n");

    for (string chain : chains) {
        output.append(chain).append("\n");
    }
    return output;
}

string print_max_chain(string chain) {
    string output = "";
    int num = 0;

    for (int i = 0; i < chain.length(); ++i) {
        char c = chain.at(i);
        if (c == ' ') {
            output.append("\n");
            num++;
            if (num > 20000) {
                throw ResultOverflowException();
            }
        }
        else {
            output.push_back(c);
        }
    }

    return output;
}